package hot100;

import java.util.Deque;
import java.util.LinkedList;

public class Solution84 {
    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = (stack.isEmpty() ? -1 : stack.peek());
            stack.push(i);
        }
        stack.clear();
        for (int i = heights.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            right[i] = (stack.isEmpty() ? heights.length - 1 : stack.peek());
            stack.push(i);
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < heights.length; i++) {
            int cur = heights[i] * (right[i] - left[i] - 1);
            max = Math.max(max, cur);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution84 solution84 = new Solution84();
        System.out.println(solution84.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
    }
}
